#_*_coding:utf-8_*_
'''
  题目 123  买卖股票的最佳时机

  给定一个数组，它的第i个元素是一支给定股票第i天的价格
  如果你最多只允许完成两笔交易（即买入和卖出一支股票一次），设计
  一个算法来计算你所能获得的最大利润。

  注意：你不能再买入股票前卖出股票，即不能同时参与多笔交易

示例 1:
  输入: [3,3,5,0,0,3,1,4]
  输出: 6
  解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
       随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。


示例 2:
  输入: [1,2,3,4,5]
  输出: 4
  解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
       注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
       因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例3：
  输入: [7,6,4,3,1] 
  输出: 0 
  解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

'''
from typing import List

class Solution:
    def maxProfit1(self, prices: List[int]) -> int:
      '''
        贪心算法，
        交易一次和交易两次的区别就在于，第二次买的时候，价格其实考虑用第一次赚的钱取补贴一部分
        
        就是minprice1 是第一次作为买卖的成本，就等于第一次买入的股票价格
            maxprofit1 是第一次买卖的收益
            而minprice2 作为第二次买卖的成本，此时不代表第二次买入股票的价格，而是第二次买入
              股票的价格减去第一次的收益
            maxprofit2 则不止是第二次买卖的收益，是两次买卖的总收益。

      '''
      minprice1, minprice2, maxprofit1, maxprofit2 = 10**9, 10**9, 0, 0
      for price in prices:
        minprice1 = min(price, minprice1)
        maxprofit1 = max(maxprofit1, price-minprice1)
        minprice2 = min(minprice2, price-maxprofit1)
        maxprofit2 = max(maxprofit2, price-minprice2)
      
      print(maxprofit1, maxprofit2)
      return maxprofit2

    def maxProfit(self, prices: List[int]) -> int:
      '''
        动态规划
          一天结束时，可能有持股，可能未持股，可能卖出一次，可能卖出两次，也可能未卖出
          所以定义状态转移数组： dp[天数][是否持股][卖出的次数]

          具体一天有六种状态：
          未持股，未卖出过股票：说明从未进行过买卖，利润为0
                dp[i][0][0]=0  
                第i天交易0次时，卖出后的累积最大利润

          未持股，卖出过1次股票：可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
                dp[i][0][1]=max(dp[i-1][1][0]+prices[i],dp[i-1][0][1])
                第i天交易1次时，卖入后的累积最大利润

          未持股，卖出过2次股票:可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）
                dp[i][0][2]=max(dp[i-1][1][1]+prices[i],dp[i-1][0][2])
                第i天交易2次时，卖出后的累积最大利润

          持股，未卖出过股票：可能是今天买的，也可能是之前买的（昨天也持股）
                dp[i][1][0]=max(dp[i-1][0][0]-prices[i],dp[i-1][1][0])
                第i天交易0次时，买入后的累积最大利润

          持股，卖出过1次股票：可能是今天买的，也可能是之前买的（昨天也持股）
                dp[i][1][1]=max(dp[i-1][0][1]-prices[i],dp[i-1][1][1])
                第i天交易1次时，买入后的累积最大利润

          持股，卖出过2次股票：最多交易2次，这种情况不存在，因为交易两次后，就不能买入了
                dp[i][1][2]=float('-inf')
                第i天交易2次时，买入后的累积最大利润

      '''
      if len(prices) < 2:
        return 0
      # 定义数组：天数，是否持有股票，卖出次数
      dp = [[[0, 0, 0],[0, 0, 0]]]*len(prices)
      dp[0][0][0] = 0
      dp[0][0][1] = 0
      dp[0][0][2] = 0
      dp[0][1][0] = -prices[0]
      dp[0][1][1] = -prices[0]
      dp[0][1][2] = -prices[0]

      for i in range(1, len(prices)):
        # 未持股，未卖出过，说明从未进行过买卖
        dp[i][0][0] = dp[i-1][0][0]
        # ************* 处理第一次买入， 第一次卖出 ************
        # 持股，未卖出过，可能是今天买的，也可能是之前买的
        dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][0][0]-prices[i])
        # 未持股，卖出一次，说明可能是今天卖的，也可能是之前卖的
        dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][1][0]+prices[i])
        # 持股，卖出一次，说明可能是今天买的，也可能是之前买的
        dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][1]-prices[i])
        # 未持股，卖出两次，说明可能是今天卖的，也可能是之前卖的
        dp[i][0][2] = max(dp[i-1][0][2], dp[i-1][1][1]+prices[i])
        # 持股，卖出两次，说明在本题中已经不可能
        dp[i][1][2] = dp[0][1][2]
      return max(dp[-1][0][1], dp[-1][0][2])




prices = [3,3,5,0,0,3,1,4]   # [7,1,5,3,6,4]  [1,2,3,4,5] [7,6,4,3,1] 
print(Solution().maxProfit(prices))
